package middle;

public class Solution_307 {

    public static void main(String[] args) {
        NumArray model = new NumArray(new int[]{-1});
//        NumArray model = new NumArray(new int[]{-1, 3, 5});
//        NumArray model = new NumArray(new int[]{1, 3, 5});
//        NumArray model = new NumArray(new int[]{0, 9, 5, 7, 3});
//        System.out.println(model.sumRange(4, 4));
//        System.out.println(model.sumRange(0, 2));
//        model.update(1, 2);
//        System.out.println(model.sumRange(0, 2));
        System.out.println(model.sumRange(0, 0));
        model.update(0, 1);
        System.out.println(model.sumRange(0, 0));
    }

    static class NumArray {

        private final int[] origin;
        private final int[] sums;

        public NumArray(int[] nums) {
            origin = new int[nums.length];
            System.arraycopy(nums, 0, origin, 0, nums.length);
            sums = new int[nums.length + 1];
            for (int i = 0; i < origin.length; i++) {
                add(i + 1, origin[i]);
            }
        }

        public void update(int index, int val) {
            add(index + 1, val - origin[index]);
            origin[index] = val;
        }

        public int sumRange(int left, int right) {
            return prefixSum(right + 1) - prefixSum(left);
        }

        private int prefixSum(int index) {
            int sum = 0;
            while (index > 0) {
                sum += sums[index];
                index -= lowBit(index);
            }
            return sum;
        }

        private void add(int index, int val) {
            while (index < sums.length) {
                sums[index] += val;
                index += lowBit(index);
            }
        }

        private int lowBit(int n) {
            return n & (-n);
        }
    }

    static class NumArray_1 {

        private final int[] origin;
        private final int[] sums;
        private final int size;

        public NumArray_1(int[] nums) {
            origin = new int[nums.length];
            System.arraycopy(nums, 0, origin, 0, nums.length);
            size = (int)Math.sqrt(nums.length);
            sums = new int[(nums.length + size -1) / size];
            for (int i = 0; i < sums.length; i++) {
                int sum = 0;
                int index = i * size, count = 0;
                for (;index < origin.length && count<size; index++,count++) {
                    sum += nums[index];
                }
                sums[i] = sum;
            }
        }

        public void update(int index, int val) {
            int i = index / size;
            sums[i] += (val - origin[index]);
            origin[index] = val;
        }

        public int sumRange(int left, int right) {
            int leftIndex = left / size;
            int rightIndex = right / size;
            if (leftIndex == rightIndex) {
                return sum(left, right);
            }
            int sum = 0;
            for (int i = leftIndex + 1; i < rightIndex; i++) {
                sum += sums[i];
            }
            for (int i = left; i < (leftIndex + 1) * size; i++) {
                sum += origin[i];
            }
            for (int i = rightIndex * size; i <= right; i++) {
                sum += origin[i];
            }
            return sum;
        }

        private int sum(int i, int j) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += origin[k];
            }
            return sum;
        }
    }
}
